package com.lw.algorithm.heap;

/**
 *最大堆
 */
public class MaxHeap {

	private int[] arr;
	private int count = 0;
	private int maxValue = 0;
	
	public MaxHeap(){
		
	}
	
	public MaxHeap(int length){
		arr = new int[length + 1];
	}

	public int getCount() {
		return count;
	}
	
	public int getMaxValue() {
		return maxValue;
	}

	public void put(int value){
		if(count == arr.length - 1){
			System.out.println("堆已满");
			return;
		}
		count ++;
		arr[count] = value;
		shitUp(count);
		maxValue = arr[1];
	}
	
	public int popMax(){
		if(count == 0){
			System.out.println("堆已为空");
			return 0;
		}
		int reValue = arr[1];
		arr[1] = arr[count];
		arr[count] = 0;
		count--;
		shitDown(1);
		maxValue = arr[1];
		return reValue;
	}
	
	private void shitUp(int index){
		int temp;
		if(index > 1){
			while(true){
				int parentIndex = index/2;
				if(arr[index] > arr[parentIndex] && parentIndex >= 1){
					temp = arr[parentIndex];
					arr[parentIndex] = arr[index];
					arr[index] = temp;
					index = parentIndex;
				}else  {
					break;
				}
			}
		}
	}
	
	private void shitDown(int index){
		int temp;
		while(true){
			int leftChild = 2 * index;
			int rightChild = 2 * index + 1;
			//表示该节点没有孩子
			if( count < leftChild ){
				break;
			//表示该节点左右孩子都有
			}else if(leftChild < count){
				if(arr[index] < arr[leftChild] && arr[index] < arr[rightChild]){
					if(arr[leftChild] > arr[rightChild]){
						temp = arr[leftChild];
						arr[leftChild] = arr[index];
						arr[index] = temp;
						index = leftChild;
					}else {
						temp = arr[rightChild];
						arr[rightChild] = arr[index];
						arr[index] = temp;
						index = rightChild;
					}
				}else if(arr[index] < arr[leftChild]){
					temp = arr[leftChild];
					arr[leftChild] = arr[index];
					arr[index] = temp;
					index = leftChild;
				}else if(arr[index] < arr[rightChild]){
					temp = arr[rightChild];
					arr[rightChild] = arr[index];
					arr[index] = temp;
					index = rightChild;
				}else {
					break;
				}
			//表示该几点只有一个左孩子
			}else if(leftChild == count){
				if(arr[index] < arr[leftChild]){
					temp = arr[leftChild];
					arr[leftChild] = arr[index];
					arr[index] = temp;
					index = leftChild;
				}else {
					break;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		MaxHeap maxHeap = new MaxHeap(5);
		maxHeap.put(34);
		maxHeap.put(45);
		maxHeap.put(65);
		maxHeap.put(89);
		maxHeap.put(100);
		
		for(int i = 0;i < 5;i++){
			System.out.println(maxHeap.popMax());
		}
	}
}
